package com.javaDemo.ti;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName: Zidianshu
 * @Auther: csy https://leetcode-cn.com/problems/re-space-lcci/solution/cong-bao-li-ru-shou-you-hua-yi-ji-triezi-dian-shu-/
 * @Date: 2021/6/21 21:12
 * @Description:
 */
public class Zidianshu {
    static TrieNode root;  //空白的根节点，设为全局变量更醒目

    public static void makeTrie(String[] dictionary) {
        for (String str : dictionary) {
            TrieNode node = root;
            for (int k = 0; k < str.length(); k++) {
                int i = str.charAt(k) - 'a';
                if (node.childs[i] == null) {
                    node.childs[i] = new TrieNode();
                }
                node = node.childs[i];
            }
            node.isWord = true; //单词的结尾
        }
    }

    /**
     * 自定义一个TrieNode类型。
     * 这里不用建一个变量来存当前节点表示的字符，
     * 因为只要该节点不为null，就说明存在这个字符
     */
    static class TrieNode {
        TrieNode[] childs;
        boolean isWord;

        public TrieNode() {
            childs = new TrieNode[26];
            isWord = false;
        }
    }
    public static int respaces(String[] dictionary, String sentence) {
        // 构建字典树
        root = new TrieNode();
        makeTrie(dictionary);   //创建字典树

        // 状态转移，dp[i] 表示字符串的前 i 个字符的最少未匹配数
        int n = sentence.length();
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            for (int idx: search(sentence, i - 1)) {
                dp[i] = Math.min(dp[i], dp[idx]);
            }
        }
        return dp[n];
    }

    // 找到 sentence 中以 endPos 为结尾的单词，返回这些单词的开头下标。
    public static List<Integer> search(String sentence, int endPos) {
        List<Integer> indices = new ArrayList<>();
        TrieNode cur = root;
        for (int i = endPos; i >= 0; i--) {
            int c = sentence.charAt(i) - 'a';
            if (cur.childs[c] == null) {
                break;
            }
            cur = cur.childs[c];
            if (cur.isWord) {
                indices.add(i);
            }
        }
        return indices;
    }

    public static void main(String[] args) {
        String[] a = {"looked", "just", "like", "her", "brother"};
        String sentence = "jesslookedjustliketimherbrother";
        // String[] a = {"im", "boy"};
        // String sentence = "imisboy";
        int as = respaces(a, sentence);
        System.out.println(as);
    }

    public static int respace(String[] dictionary, String sentence) {
        root = new TrieNode();
        makeTrie(dictionary);   //创建字典树
        int n = sentence.length();
        int[] dp = new int[n + 1];
        //这里从sentence最后一个字符开始
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = n - i;    //初始默认后面全不匹配
            TrieNode node = root;
            for (int j = i; j < n; j++) {
                int c = sentence.charAt(j) - 'a';
                if (node.childs[c] == null) {
                    //例如"abcde",i=1,j=2 可找出长度关系
                    dp[i] = Math.min(dp[i], j - i + 1 + dp[j + 1]);
                    break;
                }
                if (node.childs[c].isWord) {
                    dp[i] = Math.min(dp[i], dp[j + 1]);
                } else {
                    dp[i] = Math.min(dp[i], j - i + 1 + dp[j + 1]);
                }
                node = node.childs[c];
            }
        }
        return dp[0];
    }


}
